package cn.njupt;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

//并查集
public class UnionFind<T> {

    Map<T,Node<T>> map=new HashMap<>();
    static class Node<T>{
        T element;
        Node<T> parent=this;
        int rank=1;
        public Node(T element){
            this.element=element;
        }
    }

    public void makeSets(T t){
        if(map.containsKey(t))return;
        map.put(t,new Node<>(t));
    }

    //路径减半，每隔一个节点使其指向祖父节点
    public Node<T> findRoot(T t1){
        Node<T> node = map.get(t1);
        if(node==null)return null;
        while(!Objects.equals(node.element,node.parent.element)){
            node.parent=node.parent.parent;
            node=node.parent;
        }
        return node;
    }

    public void union(T t1,T t2){
        Node<T> ahead=findRoot(t1);
        Node<T> bhead=findRoot(t2);
        if(ahead==null || bhead==null)return;
        if(Objects.equals(ahead.element,bhead.element))return;
        if(ahead.rank<bhead.rank){
            ahead.parent=bhead;
        }else if(ahead.rank>bhead.rank){
            bhead.parent=ahead;
        }else{
            ahead.parent=bhead;
            bhead.rank+=1;
        }

    }

    public T find(T t1){
        Node<T> root = findRoot(t1);
        return root==null?null:root.element;
    }


    public boolean isSame(T t1,T t2){
        return Objects.equals(find(t1),find(t2));
    }
}
